Many network services use packet classification, such as routing, access control, policy-based routing, quality-of-service differentiation, billing, etc. In one application a packet classifier examines packets to determine whether to forward or filter a packet and to apply an appropriate class of service to the packet. Classification is typically based on reading the data in headers of the packet, such as addresses, port numbers, or other fields in headers and tail bits of a data packet. In the simplest implementations, the values in the appropriate fields are applied to lookup tables and when there is a match, a corresponding rule or a policy is applied to the packet.
Some packet classification systems perform binary pattern matching using Access Control Lists (ACLs). ACLs consist of bit patterns or rules that are used to classify bits. Filter ACL are used to determine whether a given bit field is admitted or not. ACLs are used in packet based communication networks where ACL rules may be based on address and port information in the packet header. ACLs may also be based on fields deeper into the packet for Deep Packet Inspection. Policy ACLs are used in packet based networks to classify traffic into classes which each receive separate treatment, for example in terms of forwarding, queuing, rate limitation, and marking. For complete packet routing all of these lists must be examined and matched to incoming packets. In some applications, matching may be done by different routers and some ACLs may be ignored in order to save time.
To allow for many different types of packets to be routed at high speed, packet classification has been advanced beyond simple lookup tables. Some systems use a staged lookup process in which a first part of the package is examined. The result of that examination is used to select the second part to be examined in a branched decision process. This classification continues with different branches being taken until the final classification is reached. While more steps are used, each step in the process is simplified and if the system is well-designed, then classification is faster. This can be referred to as tree-based classification in which the first decision is a root node and each resulting decision is a branch node. The last branch node is referred to as a leaf node. After the leaf node process, the packet is classified.
In order to route a larger variety of different packets more quickly, pattern matching algorithms must be improved in terms of lookup time, processing and memory usage. This is made more difficult by the cost associated with implementing algorithms for different types of ACLs such as IPv4 (Internet Protocol version 4), IPv6 (IP version 6), Ethernet, ATM (Asynchronous Transfer Mode), etc. TCAM (Ternary Content Associated Memory) hardware accelerated algorithms have been developed to address these problems. TCAM uses parallel hardware to check for all rules in parallel. While the hardware is fast it is expensive and requires large memory resources and high power consumption. In applications with thousands of sessions where individual ACLs are required, the resources of a TCAM system may run out.